#include "headfiles.h"

// There are n coins in a line. (Assume n is even). Two players take turns to 
// take a coin from one of the ends of the line until there are no more coins 
// left. The player with the larger amount of money wins.

// Would you rather go first or second? Does it matter? Assume that you go 
// first, describe an algorithm to compute the maximum amount of money you 
// can win.

int calcMaxWinAmount(int *a, int n) {
    if (a == NULL ||
        n <= 0) {
        return -1;
    }

    int elem_num = (n + 1) * (n + 1);
    int *max_win = new int[elem_num];
    if (max_win == NULL) {
        return -1;
    }
    memset(max_win, 0, sizeof(int) * elem_num);

    // Calculate the sume table. elem(i, j) is the sum from elem i to 
    // elem j, inclusive
    int loc, i, j, sum;
    for (i = 1; i <= n; i++) {
        sum = 0;
        loc = i * (n + 1) + i;
        for (j = i; j <= n; j++) {
            sum += a[j - 1];
            loc = i * (n + 1) + j;
            max_win[loc] = sum;
        }
    }

    // Calculate the max win table, from the bottom-right corner
    // to the top-left corner
    for (i = n - 1; i >= 1; i--) {
        for (j = i + 1; j <= n; j++) {
            int loc1 = (i + 1) * (n + 1) + j;
            int loc2 = i * (n + 1) + j - 1;
            loc = i * (n + 1) + j;
            int val = (max_win[loc1] > max_win[loc2]) ? 
                        max_win[loc2] : max_win[loc1];
            max_win[loc] = max_win[loc] - val;
        }
    }

    // calculate sum
    sum = 0;
    for (i = 0; i < n; i++) {
        sum += a[i];
    }
    int max_win_val = max_win[2 * n + 1];

    delete max_win;

    return max_win_val + max_win_val - sum;
}

